package srcInterviewPrep;

public final class NBitAdder
{
    public static char[] AddBits(char[] a, char[] b)
    {
        // check: a.length == b.length

        int n = a.length;

        char[] sum = new char[n+1];

        char curCarry = '0';

        for (int i = n-1; i>=0; --i)
        {
            SumCarryPair scPair = FullAdder(a[i], b[i], curCarry);

            curCarry = scPair.carry;

            sum[i+1] = scPair.sum;
        }

        sum[0] = curCarry;

        return sum;
    }

    private static SumCarryPair FullAdder(char a, char b, char cin)
    {
        char s = '0';
        char c = '0';

        if (a == '1' && b == '0' && cin == '0')
        {
            s = '1';
        }
        else if (a == '0' && b == '1' && cin == '0')
        {
            s = '1';
        }
        else if (a == '1' && b == '1' && cin == '0')
        {
            c = '1';
        }
        else if (a == '0' && b == '0' && cin == '1')
        {
            s = '1';
        }
        else if (a == '1' && b == '0' && cin == '1')
        {
            c = '1';
        }
        else if (a == '0' && b == '1' && cin == '1')
        {
            c = '1';
        }
        else if (a == '1' && b == '1' && cin == '1')
        {
            c = '1';
            s = '1';
        }

        return new SumCarryPair(s,c);
    }

    private static final class SumCarryPair
    {
        private char sum;
        private char carry;

        private SumCarryPair(char sum, char carry)
        {
            this.sum = sum;
            this.carry = carry;
        }
    }
}
